//
// This software is now distributed according to
// the Lesser Gnu Public License. Please see
// http://www.gnu.org/copyleft/lesser.txt for
// the details.
// -- Happy Computing!
//
package com.stevesoft.pat;

import java.util.BitSet;
import java.util.Vector;

/**
 * Uses table lookup to match [] type constructs, but only if it can use a
 * lookup table 256 bits in size. It is impractical to make a table if it is too
 * large.
 */
public class FastBracket extends Bracket {

	int min, max;
	BitSet bs;

	FastBracket(boolean n) {
		super(n);
	}

	// This routine can optimize a bracket, possibly
	// it will replace it with a FastBracket.
	static Bracket process(Bracket b, boolean ignc) {
		Vector v = b.v;
		b.pv = null;
		try {
			// Expand out the vector to make separate
			// entries for other cases if ignoreCase is
			// turned on.
			Vector nv = v;
			if (ignc) {
				nv = new Vector();
				for (int i = 0; i < v.size(); i++) {
					Pattern p = (Pattern) v.elementAt(i);
					nv.addElement(p);
					if (p instanceof oneChar) {
						oneChar oc = (oneChar) p;
						nv.addElement(new oneChar(oc.altc));
					}
					else if (p instanceof Range) {
						Range ra = (Range) p;
						nv.addElement(new Range(ra.altlo, ra.althi));
					}
				}
			}
			v = nv;
			// Bubble sort, make sure elements
			// are in order. This will allow us
			// to merge them.
			for (int i = 0; i < v.size() - 1; i++) {
				for (int j = 0; j < v.size() - 1; j++) {
					char c1 = getl(v.elementAt(j));
					char c2 = getl(v.elementAt(j + 1));
					if (c2 < c1) {
						Object o = v.elementAt(j);
						v.setElementAt(v.elementAt(j + 1), j);
						v.setElementAt(o, j + 1);
					}
				}
			}
			nv = new Vector();
			// merge -- remove overlaps
			Pattern p = (Pattern) v.elementAt(0);
			nv.addElement(p);
			for (int i = 1; i < v.size(); i++) {
				if (geth(p) + 1 >= getl(v.elementAt(i))) {
					Pattern p2 = (Pattern) v.elementAt(i);
					char lo = min(getl(p), getl(p2));
					char hi = max(geth(p), geth(p2));
					nv.setElementAt(p = mkelem(lo, hi), nv.size() - 1);
				}
				else {
					p = (Pattern) v.elementAt(i);
					nv.addElement(p);
				}
			}
			b.v = v = nv;
		} catch (RegSyntax e) {
			e.printStackTrace();
		}
		// We don't want these things to be empty.
		Vector negv = neg(v);
		if (v.size() == 1)
			return b;
		if (negv.size() == 1) {
			b.v = negv;
			b.neg = !b.neg;
			return b;
		}
		// Now consider if we can make a FastBracket.
		// Uses a BitSet to do a lookup.
		FastBracket fb = newbrack(v, b.neg);
		if (fb == null)
			fb = newbrack(negv, !b.neg);
		if (fb != null) {
			fb.parent = b.parent;
			fb.next = b.next;
			return fb;
		}
		// return the normal Bracket.
		return b;
	}

	// Build a FastBracket and set bits. If this can't
	// be done, return null.
	final static FastBracket newbrack(Vector v, boolean neg) {
		FastBracket fb = new FastBracket(neg);
		fb.v = v;
		if (v.size() == 0)
			return null;
		fb.min = getl(v.elementAt(0));
		fb.max = geth(v.elementAt(v.size() - 1));
		if (fb.max - fb.min <= 256) {
			fb.bs = new BitSet(fb.max - fb.min + 1);
			for (int i = 0; i < v.size(); i++) {
				Object o = v.elementAt(i);
				int min0 = getl(o) - fb.min;
				int max0 = geth(o) - fb.min;
				for (int j = min0; j <= max0; j++)
					fb.bs.set(j);
			}
			return fb;
		}
		return null;
	}

	// Negate a sorted Vector. Applying this
	// operation twice should yield the same Vector
	// back.
	final static Vector neg(Vector v) {
		try {
			Vector nv = new Vector();
			if (v.size() == 0) {
				nv.addElement(new Range((char) 0, (char) 65535));
				return nv;
			}
			int p0 = getl(v.elementAt(0));
			if (p0 != 0)
				nv.addElement(mkelem((char) 0, (char) (p0 - 1)));
			for (int i = 0; i < v.size() - 1; i++) {
				int hi = getl(v.elementAt(i + 1)) - 1;
				int lo = geth(v.elementAt(i)) + 1;
				nv.addElement(mkelem((char) lo, (char) hi));
			}
			int pN = geth(v.lastElement());
			if (pN != 65535)
				nv.addElement(mkelem((char) (pN + 1), (char) 65535));
			return nv;
		} catch (RegSyntax rs) {
			return null;
		}
	}

	// Make either a Range or oneChar Object, depending on which
	// is appropriate.
	final static Pattern mkelem(char lo, char hi) throws RegSyntax {
		return lo == hi ? (Pattern) (new oneChar(lo)) : (Pattern) (new Range(lo, hi));
	}

	static final char min(char a, char b) {
		return a < b ? a : b;
	}

	static final char max(char a, char b) {
		return a > b ? a : b;
	}

	// getl -- get lower value of Range object,
	// or get value of oneChar object.
	final static char getl(Object o) {
		Pattern p = (Pattern) o;
		if (p instanceof Range)
			return ((Range) p).lo;
		return ((oneChar) p).c;
	}

	// geth -- get higher value of Range object,
	// or get value of oneChar object.
	final static char geth(Object o) {
		Pattern p = (Pattern) o;
		if (p instanceof Range)
			return ((Range) p).hi;
		return ((oneChar) p).c;
	}

	// This is the easy part!
	public int matchInternal(int pos, Pthings pt) {
		if (pos >= pt.src.length() || Masked(pos, pt))
			return -1;
		char c = pt.src.charAt(pos);
		return (neg ^ (c >= min && c <= max && bs.get(c - min))) ? nextMatch(pos + 1, pt) : -1;
	}
}
